// 2025/11/20
// 寻找两个正序数组的中位数

class Solution {
    // 寻找两个有序数组的第k小的数
    int findK(vector<int>& nums1, vector<int>& nums2, int k)
    {
        int m = nums1.size(), n = nums2.size();
        // nums1以i为起点，nums2以j为起点，向后查找第k个数
        int i = 0, j = 0;
        while(true)
        {
            // nums1全部排除
            if(i == m) return nums2[j + k - 1];
            // nums2全部排除
            if(j == n) return nums1[i + k - 1];
            // k为1，代表下一个数即是第k个数
            if(k == 1) return min(nums1[i], nums2[j]);

            // 从起点开始，各自找到第k/2个数
            int index1 = min(m, i + k / 2) - 1, index2 = min(n, j + k / 2) - 1;
            // nums1的第k/2个数小于nums2的，那这k/2个数一定在第k个数之前，排除
            if(nums1[index1] <= nums2[index2])
            {
                // 从k中排除掉这k/2个数
                k -= index1 + 1 - i;
                // nums1的起点设置为下一个数
                i = index1 + 1;
            }
            else // 同理
            {
                k -= index2 + 1 - j;
                j = index2 + 1;
            }
        }
    }
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len = nums1.size() + nums2.size();
        if(len % 2 == 1)
        {
            return findK(nums1, nums2, len / 2 + 1);
        }
        else
        {
            return ((double)findK(nums1, nums2, len / 2) + findK(nums1, nums2, len / 2 + 1)) / 2;
        }
    }
};